package com.bo.day20240924;

/**
 * 二叉树的后继节点
 * 定义：某个节点的后继节点，就是中序遍历中该节点的下一个节点
 * 13 12 8 4 9 2 10 5 11 1 6 3 7
 * 9的后继节点就是2
 * 实现思路
 * 1. 如果该节点有右子树，则该节点的后继节点就是右子树的最左节点
 * 2. 如果该节点没有右子树，则该节点的后继节点就是该节点的父节点，直到找到一个节点的父节点的左孩子是该节点，则该节点的父节点就是该节点的后继节点
 *
 * @Author: gpb
 * @Date: 2024/9/24 16:27
 * @Description:
 */
public class SuccessorNode {
    public static class Node {
        public int value;
        public Node left;
        public Node right;
        public Node parent;

        public Node (int v) {
            value = v;
        }
    }

    public static Node getSuccessorNode (Node node) {
        if (node == null) {
            return null;
        }
        // 存在右子树,则后继节点就是右子树的最左节点
        if (node.right != null) {
            // 右子树最左节点
            return getLeftNode(node);
        }
        // 如果该节点没有右子树，则该节点的后继节点就是该节点的父节点，直到找到一个节点的父节点的左孩子是该节点，则该节点的父节点就是该节点的后继节点
        Node parent = node.parent;
        while (parent != null && parent.right == node) {
            node = parent;
            parent = parent.parent;
        }
        return parent;
    }

    /**
     * 右子树最左节点
     *
     * @param node
     * @return
     */
    private static Node getLeftNode (Node node) {
        if (node == null) {
            return null;
        }
        while (node.left != null) {
            node = node.left;
        }
        return node;
    }


    public static void pos (Node node) {
        if (node == null) {
            return;
        }
        pos(node.left);
        System.out.print(node.value + " ");
        pos(node.right);
    }

    public static void main (String[] args) {
        Node node = new Node(1);
        node.left = new Node(2);
        node.right = new Node(3);
        node.left.left = new Node(4);
        node.left.right = new Node(5);
        node.right.left = new Node(6);
        node.right.right = new Node(7);
        node.left.left.left = new Node(8);
        node.left.left.right = new Node(9);
        node.left.right.left = new Node(10);
        node.left.right.right = new Node(11);
        node.left.left.left.left = new Node(12);
        node.left.left.left.left.left = new Node(13);
        pos(node);
        System.out.println();
        System.out.println("========================================");
        Node head = new Node(6);
        head.parent = null;
        head.left = new Node(3);
        head.left.parent = head;
        head.left.left = new Node(1);
        head.left.left.parent = head.left;
        head.left.left.right = new Node(2);
        head.left.left.right.parent = head.left.left;
        head.left.right = new Node(4);
        head.left.right.parent = head.left;
        head.left.right.right = new Node(5);
        head.left.right.right.parent = head.left.right;
        head.right = new Node(9);
        head.right.parent = head;
        head.right.left = new Node(8);
        head.right.left.parent = head.right;
        head.right.left.left = new Node(7);
        head.right.left.left.parent = head.right.left;
        head.right.right = new Node(10);
        head.right.right.parent = head.right;
        pos(head);
        System.out.println();
        Node test = head.left.left;
        System.out.println(test.value + " next: " + getSuccessorNode(test).value);
        test = head.left.left.right;
        System.out.println(test.value + " next: " + getSuccessorNode(test).value);
        test = head.left;
        System.out.println(test.value + " next: " + getSuccessorNode(test).value);
        test = head.left.right;
        System.out.println(test.value + " next: " + getSuccessorNode(test).value);
        test = head.left.right.right;
        System.out.println(test.value + " next: " + getSuccessorNode(test).value);
        test = head;
        System.out.println(test.value + " next: " + getSuccessorNode(test).value);
        test = head.right.left.left;
        System.out.println(test.value + " next: " + getSuccessorNode(test).value);
        test = head.right.left;
        System.out.println(test.value + " next: " + getSuccessorNode(test).value);
        test = head.right;
        System.out.println(test.value + " next: " + getSuccessorNode(test).value);
        test = head.right.right; // 10's next is null
        System.out.println(test.value + " next: " + getSuccessorNode(test));
    }

}
